\documentclass[twoside,colorback,accentcolor=tud4c,11pt]{tudreport}
\usepackage{ngerman}

\usepackage[utf8]{inputenc}

\usepackage{listings}
\lstset{
numbers=left,
numberstyle=\footnotesize,
frame=l,
breaklines=true,
basicstyle=\footnotesize,
showstringspaces=false
}

\usepackage[stable]{footmisc}
\usepackage[ngerman,pdfview=FitH,pdfstartview=FitV]{hyperref}

\usepackage{booktabs}
\usepackage{multirow}
\usepackage{longtable}

\newlength{\longtablewidth}
\setlength{\longtablewidth}{0.675\linewidth}

\title{Low-Level Synthese}
\subtitle{BDD-Library}
\subsubtitle{Wilko Kunert, Alexander Schleich}
\lowertitleback{\hfill\today}
\institution{Rechnersysteme}
 
\begin{document}
\maketitle

\tableofcontents

\chapter{Benutzung} 
\label{chapter:Benutzung}

Die BDD-Library wird aus der Kommandozeile mit den gewünschten Argumenten aufgerufen. Alle verfügbaren Argumente und deren Funktion werden durch den Aufruf mit dem Argument \textit{-h} angezeigt: 

\vspace*{5mm}
usage: bddlib [-c <variables> | -w] -d <dot-executable> -f <blif-files> [-h] [-q | -r]\\
\hspace*{7mm}-c,--customOrder <variables>~~~~~~~~~~Specify custom variable order (separated with commas).\\
\hspace*{7mm}-d,--dot <dot-executable>~~~~~~~~~~~~~~~Create *.png-graphs with Graphviz/dot.\\
\hspace*{7mm}-f,--files <blif-files>~~~~~~~~~~~~~~~~~~~~~~~~~~Specify blif-files (separated with commas) to process.\\
\hspace*{7mm}-h,--help~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Display this help.\\
\hspace*{7mm}-q,--qreduce~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Quasireduce resulting BDD (QROBDD).\\
\hspace*{7mm}-r,--reduce~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Reduce resulting BDD (ROBDD).\\
\hspace*{7mm}-s,--semiCustomOrder <variables>~~Specify custom variable order (separated with commas) and\\
\hspace*{16mm}wildcard ('*'), which is replaced with missing variables determined by weight-heuristics.\\
\hspace*{7mm}-w,--weightOrder~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Order variables with weight-heuristics.
\vspace*{5mm}
 
Anhand eines einfachen Beispiels sollen die Funktionen der einzelnen Argumente näher erläutert werden. Hierfür wird folgendes BLIF-Beschreibung (example.blif) verwendet:

\vspace*{5mm}
\hspace*{3mm}.names a b c d e x\\
\hspace*{7mm}10-11 1\\
\hspace*{7mm}01-11 1\\
\vspace*{5mm}

Der einfachste Aufruf, der nur die obligatorischen Argumente beinhaltet sieht folgendermaßen aus:

\vspace*{5mm}
\hspace*{3mm}bddlib -d /usr/bin/dot -f example.blif
\vspace*{5mm}

Das Ergebnis sieht des Aufrufs ist in Abbildung~\ref{fig:1_example} zu sehen. Abbildung~\ref{fig:2_example} zeigt den reduzierten Baum, der durch das Hinzufügen des Arguments \textit{-r} ensteht. Einen quasi-reduzierten Baum (Abbildung~\ref{fig:3_example}) erzeugt man mithilfe des Arguments \textit{-q}.

\begin{figure}[h]
\centering
\includegraphics[width=\linewidth]{graphics/1_example_blif.png}
\caption{OBDD}
\label{fig:1_example}
\end{figure}


\begin{figure}[h]
\centering
\includegraphics[width=.5\linewidth]{graphics/2_example_blif.png}
\caption{ROBDD}
\label{fig:2_example}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics[width=.5\linewidth]{graphics/3_example_blif.png}
\caption{QROBDD}
\label{fig:3_example}
\end{figure}

Die Reihenfolge der Variabeln kann durch die Argumente \textit{-c}, \textit{-w} und \textit{-s} beeinflusst werden. Im ersten Fall gibt man die gewünschte Variablenreihenfolge händisch an (z.B. \textit{c,e,a,d,b}), im zweiten Fall wird die Reihenfolge durch die Weight-Heuristik festgelegt, der dritte Fall kombiniert die beiden Verfahren: Man gibt die gewünschte Reihenfolge inklusive einer Wildcard an - die Wildcard wird dann durch die übrigen Variablen, deren Reihenfolge nach der Weight-Heuristik bestimt wird, ersetzt. Das Ergebnis des Aufrufs \textit{bddlib~-d~/usr/bin/dot~-f~example.blif~-q~-c~c,e,a,d,b} ist in Abbildung~\ref{fig:4_example}, das Ergebnis des Aufrufs \textit{bddlib~-d~/usr/bin/dot~-f~example.blif~-r~-w} in Abbildung~\ref{fig:5_example} zu sehen. Die Abbildung~\ref{fig:6_example} zeigt den Aufruf \textit{bddlib~-d~/usr/bin/dot~-f~example.blif~-q~-s c,d,*,a}. 

\begin{figure}[h]
\centering
\includegraphics[width=.5\linewidth]{graphics/4_example_blif.png}
\caption{QROBDD mit vorgegebener Variablenreihenfolge}
\label{fig:4_example}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics[width=.5\linewidth]{graphics/5_example_blif.png}
\caption{ROBDD nach Weight-Heuristik}
\label{fig:5_example}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics[width=.5\linewidth]{graphics/6_example_blif.png}
\caption{QROBDD mit teilweise vorgegebener Reihenfolge}
\label{fig:6_example}
\end{figure}


\chapter{Implementierung}

\section{Boolesche Funktionen}

Zum Einlesen der BLIF Dateien haben wir ein einfaches Framework erstellt,
welches das Modellieren von Booleschen Funktionen erlaubt. \\
Eingelesen werden die Dateien von der Klasse ``BLIFReader'', welche ein Modell
des Frameworks anlegt. Momentan unterstützen wir nur einfache BLIF Dateien im
genannten Format, d.h. nur das On-Set zur Definition von DNFs z.B.:
\\

\vspace*{5mm}
\hspace*{3mm}.names a b c d e x\\
\hspace*{7mm}10-11 1\\
\hspace*{7mm}01-11 1\\
\vspace*{5mm}


Ein UML-Diagramm des Frameworks ist auf \ref{fig:bexp_uml} zu sehen.
Für unsere Anforderung genügen And, Or und Not Gatter sowie das Anlegen
von Variablen. Eine Boolesche Funktion besitzt eine Anzahl an Input Variablen, 
eine Output Variable sowie eine Input Expression. \\
Das genannte Beispiel in der String-Repräsentation liest sich folgendermaßen:
\\

x = ((ab'de)+(a'bde))

 

\begin{figure}[h]
\centering
\includegraphics[width=.8\linewidth]{graphics/BExpUml.pdf}
\caption{Framework für Boolesche Funktionen}
\label{fig:bexp_uml}
\end{figure}

\section{Variablenreihenfolge}

Momentan bieten wir zwei verschiedene Strategien an, um eine
Variablenreihenfolge festzulegen. Zum einen die
``UserDefinedVariableOrderStrategy'' welche eine vom Nutzer eingegebene
Variablenreihenfolge erwartet (siehe \nameref{chapter:Benutzung} -c Argument),
zum anderen die WeightHeuristicVariableOrderStrategy, die eine Reihenfolge nach der
Weight-Heuristik berechnet (siehe \ref{fig:var_order}). \\
Auch möglich ist eine Mischung zwischen selbst angegebener Reihenfolge und
Weight Heuristik (siehe \nameref{chapter:Benutzung} -s Argument).
 
\begin{figure}[h]
\centering
\includegraphics[width=.8\linewidth]{graphics/VarOrderUml.pdf}
\caption{Strategien zur Variablenreihenfolge}
\label{fig:var_order}
\end{figure} 

\section {Shannon-Expansion}
 
Um aus der Booleschen Funktion ein BDD erzeugen zu können, muss zuerst die
Shannon-Expansion auf die Funktion angewendet werden. Hierzu kann die Klasse
``ShannonExpander'' mit der statischen Methode ``expand'' benutzt werden, die
eine Variablenreihenfolge und einen Booleschen Ausdruck erwartet. \\

Mit der Weight-Heuristik ergibt sich für das Beispiel folgender Boolescher
Ausdruck:
\\
\begin{figure}[h]
\centering
\includegraphics[width=1\linewidth]{graphics/ShannonExpanded_cropped.pdf}
\caption{nach Shannon-Expansion}
\label{fig:shannon_expand}
\end{figure}

Für die Shannon-Expansion wird eine weitere Klasse ``Evaluator'' benötigt, 
die einen Booleschen Ausdruck nach einer übergebenen Variablenbelegung
auswerten kann. \\
Diese Klasse kann auch dazu verwendet werden einen bereits expandierten
Ausdruck nach einigen Regeln zu reduzieren, indem man eine leere
Variablenbelegung angibt. \\

Für den genannten Ausdruck ergibt sich so: \\\\
 
(d(e((ba')+(b'a)))) \\

was in diesem Fall bereits dem ROBDD entspricht. Eine nachträgliche Reduktion
würde somit entfallen, bzw. evtl. schneller gehen.
 
\section{BDD Erzeugung}

Zum Erzeugen von BDDs haben wir folgendes Framework erstellt (siehe \ref{fig:bdd_uml})
Grundsätzlich besteht ein BDD aus Knoten die mit anderen Knoten über eine ``zero''
und eine ``one'' Kante verbunden ist. \\ Terminals dürfen keine weiteren Knoten
verbinden. \\
Die Klasse BDDCreator bietet eine Methode an die eine Transformation Boolescher
Ausdruck -> BDD ermöglicht. Der übergeben Ausdruck muss bereits im expandierten
Zustand vorliegen, damit ein korrektes BDD erstellt werden kann. \\
Weiterhin kann beim transformieren eine Reduktionsstrategie angegeben werden,
die das erzeugte BDD reduziert.

\section{DOT Diagramm}

Zur visuellen Darstellung bieten wir mit der Klasse ``DOTCreator'' eine kleine
Api an, die aus einem BDD eine Datei im .dot-Format erstellt und diese in eine
.png umwandelt (Nur möglich falls Graphviz/dot installiert ist und der korrekte
Pfad dazu angegeben wurde)

\begin{figure}[h]
\centering
\includegraphics[width=1\linewidth]{graphics/BDDUml.pdf}
\caption{BDD Framework}
\label{fig:bdd_uml}
\end{figure}

\end{document}
